#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 110;
const int inf = 1 << 27;
int n, m, sitex, sitey, color, ans = inf;
int tempprice;
int map[maxn][maxn];      //地图
int dx[] = {1, -1, 0, 0}; //四个方向
int dy[] = {0, 0, 1, -1};
bool vis[maxn][maxn] = {false}; //标记是否走过
int minprice[maxn][maxn];       //记录每个位置的最小价格

void dfs(int x, int y, int flag) // flag记录是否刚花2块钱变过颜色
{
    if (tempprice >= minprice[x][y]) //剪枝：当前价格>最小价格，后面不用找了
        return;
    minprice[x][y] = tempprice; //能走到这代表有更小的价格，于是更新最小价格

    if (x == m && y == m) //到达终点，比较price和ans，price小则更新ans
    {
        ans = min(ans, tempprice);
        return;
    }

    for (int i = 0; i < 4; i++)
    {
        int newx = x + dx[i]; //下一个格子
        int newy = y + dy[i];
        if (newx >= 1 && newx <= m && newy >= 1 && newy <= m && vis[newx][newy] == false)
        // 判断没有出界，没有访问过
        {
            if (map[newx][newy] == 0 || map[newx][newy] == 1)
            //为0或1代表有颜色
            {
                if (map[newx][newy] == map[x][y])
                //如果下一个格子和当前格子颜色相同，price不增加
                {

                    vis[newx][newy] = 1;
                    dfs(newx, newy,0); //回溯一下
                    vis[newx][newy] = 0;
                }
                else if (map[newx][newy] != map[x][y])
                //如果下一个格子和当前格子颜色不相同，并且不是无色，price+1
                {
                    tempprice += 1;
                    vis[newx][newy] = 1;
                    dfs(newx, newy,0);
                    vis[newx][newy] = 0;
                    tempprice -= 1;
                }
            }
            else //都是-1，即为无色
            {
                if (flag == 0) //上一个没用过2块钱变色
                {
                    map[newx][newy] = map[x][y];
                    tempprice += 2;
                    vis[newx][newy] = 1;
                    dfs(newx, newy,1);
                    /*回溯map变回无色-1，并不是为了走过之后离开要变回无色-1，
                    这里不用考虑，因为回溯后相当于没走过这个格子，如果下一步这里
                  没有回溯就代表这条路可以走，那么vis为1，也不会再访问（个人理解）*/
                    vis[newx][newy] = 0;
                    map[newx][newy] = -1;
                    tempprice -= 2;
                }
            }
        }
    }
}

int main()
{

    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            map[i][j] = -1; //全部赋值为-1，代表无色

    while (n--)
    {
        cin >> sitex >> sitey >> color;
        map[sitex][sitey] = color; //把有色的格子更新
    }

    memset(minprice, 0x3f, sizeof(minprice));

    vis[1][1] = 1;
    dfs(1, 1, 0); //位置1，1 ； price=0 ； flag=0；

    if (ans == 1 << 27) //如果ans没更新，就无法到达，输出-1，else输出ans
        cout << -1;
    else
        cout << ans;
    return 0;
}
